package _go

/*面试题 02.06. 回文链表
难度
简单

66

收藏

分享
切换为英文
接收动态
反馈
编写一个函数，检查输入的链表是否是回文的。



示例 1：

输入： 1->2
输出： false
示例 2：

输入： 1->2->2->1
输出： true


进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	//计算 链表长度
	Len := GetLen(head)

	//翻转链表的前置节点
	pre := &ListNode{}

	curr := head
	for i := 0; i < Len/2; i++ {
		Tmp := curr.Next
		curr.Next = pre
		pre = curr
		curr = Tmp
	}

	//判断奇偶 奇数要剔除一个节点
	if Len%2 != 0 {
		curr = curr.Next
	}
	// fmt.Printf("len %d head %s pre %s\n",Len,curr, pre)

	//对比两个链表
	for curr != nil && pre != nil {
		if curr.Val != pre.Val {
			return false
		}
		curr = curr.Next
		pre = pre.Next
	}
	// fmt.Printf("len %d head %s pre %s\n",Len,curr, pre)

	if curr == nil && pre.Val != 0 {
		return false
	}

	return true
}

func GetLen(head *ListNode) (i int) {
	for i = 0; head != nil; i++ {
		head = head.Next
	}
	return i
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
//数组判断回文
func isPalindrome(head *ListNode) bool {
	//借助切片来判断
	if head == nil {
		return true
	}

	sliceHead := []int{}

	for head != nil {
		sliceHead = append(sliceHead, head.Val)
		head = head.Next
	}

	i, j := 0, len(sliceHead)-1

	for i < j {
		if sliceHead[i] != sliceHead[j] {
			return false
		}
		i++
		j--
	}
	return true
}
